"""
Graph
Programmer: Oscar Chang From Ron Smith
Date: April 30, 2014
"""

debug = False

class Queue():

    """
        Queue Class : (Enter)Rear ------------Front(Exit)
        First in First Out
    """
    
    def __init__(self):
        self.items = []

    def __str__(self):
        return str(self.items)

    def __repr__(self):
        return "Queue" + str(self)

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        return self.items.pop(0)

    def isEmpty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)


class Vertex():
    def __init__(self,key,pred=None,color=None,distance=0):
        self.id = key
        self.connectedTo = {}   
        self.pred = pred
        self.color = color
        self.distance = distance

    def addNeighbor(self,neighbor,weight=0):
        self.connectedTo[neighbor]=weight
 
    def __str__(self):
        return "{}(pred={},color={},distance={})\n  connectedTo {}".format(
            self.id,self.pred,self.color,self.distance,self.connectedTo)

    def getId(self):                        #Note: Id's may not be reset.
        return self.id

    def getNeighbors(self):
        return self.connectedTo.keys()      #Returns keys (not vertices)

    def setPredecessor(self,pred):
        self.pred = pred
        
    def getPredecessor(self):
        return self.pred
    

    def setColor(self,c):
        self.color = c

    def getColor(self):
        return self.color

    def setDistance(self,d):
        self.distance = d

    def getDistance(self):
        return self.distance

    def show(self,select=31):
        """String with format determined by bits of select (31=all)

           1:Predecessor, 2:Color, 4:Distance, 8:ConnectedTo 16:weight
           e.g. show(select = 10) shows connectedTo and Color
        """
        bit=lambda x,y:(x>>y)%2
        s = str(self.id)
        pList = []
        if bit(select,0)>0: #pred
            pList.append("pred="+str(self.pred))
        if bit(select,1)>0: #color
            pList.append("color="+str(self.color))
        if bit(select,2)>0: #dist
            pList.append("distance="+str(self.distance))
        if len(pList)>0:
            pStr = "("+(",".join(pList))+")"
        else:
            pStr = ""
        if bit(select,3) >0 and bit(select,4) >0: #connectedTo
            c = "\n  connectedTo {}".format(list(self.connectedTo.items()))
        elif bit(select,3)>0:
            c = "\n  connectedTo {}".format(list(self.connectedTo.keys()))
        else:
            c = ""
        return s+pStr+c        

class Graph():
    def __init__(self):
        self.vertexList = {}

    def addVertex(self,key,pred=None,color=None,dist=None):
        """Add vertex id=key to graph. Replaces existing vertex with same id."""
        newVertex = Vertex(key,pred,color,dist)
        self.vertexList[key] = newVertex
        #Note no return value

    def getVertex(self,key):            #Converts key to vertex
        if key in self.vertexList:
            return self.vertexList[key]
        else:
            return None

    def __contains__(self,key):
        """Expression 'key in graph' is defined."""
        return key in self.vertexList

    def addEdge(self,key1,key2,cost=0):
        """Add vertices key1,key2 if not already present,and insert edge."""
        if key1 not in self:
            self.addVertex(key1)
        if key2 not in self:
            self.addVertex(key2)
        self.getVertex(key1).addNeighbor(key2,cost)

    def getVertices(self):
        return self.vertexList.keys()

    def __iter__(self):
        """for v in graph: ... iterates over vertices (not keys)."""
        return iter(self.vertexList.values())
        
    def bfs(self,start):
        """Breadth First Search from vertex.id = start.

           Resets payloads of each vertex as follows:
               distance = shortest path from start.
               pred = a vertex on shortest path
               color = White: Not visited
                       Gray: In Queue (Neighbors not all checked)
                       Black: All neighbors checked
        """
        for v in self:                  #Initialize all payloads:
            v.setColor("White")         #White => Not Visited
            v.setPredecessor(None)
            v.setDistance(0)
        q = Queue()
        q.enqueue(self.getVertex(start)) #Enqueue start vertex
        while not q.isEmpty():
            v = q.dequeue()
            dist = v.getDistance()
            for key in v.getNeighbors():
                w = self.getVertex(key)
                if w.getColor()=="White":
                    w.setColor("Gray")
                    w.setDistance(dist+1)
                    w.setPredecessor(v.id)
                    q.enqueue(w)
            v.setColor("Black")
        if debug:self.show(15)          #Shows all but weight

    def minPath(self,start,end):
        self.bfs(start)
        current = self.getVertex(end)
        path = []
        while (current.getColor()=="Black" and
               current.getPredecessor() != None):
            path = [current.id]+path
            current = self.getVertex(current.pred)
        if current.getColor()=="Black":
            path = [current.id]+path
        return path
            
    def show(self,select=31):
        """List vertices w/ info determined by bits of select in [1..31]
           1:Predecessor, 2:Color, 4:Distance, 8:ConnectedTo 16:weight
           e.g. show(select = 10) shows Color and connectedTo
        """
        for v in self:
            print(v.show(select))
                
            
    
